package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.PriorityQueue;

public class Code24_DijkstraKthSmallest {

	public static class Edge {
		public int weight;
		public Node from;
		public Node to;

		public Edge(int weight, Node from, Node to) {
			this.weight = weight;
			this.from = from;
			this.to = to;
		}
	}

	public static class Node {
		public int value;
		public int in;
		public int out;
		public String path;
		public ArrayList<Node> nexts;
		public ArrayList<Edge> edges;

		public Node(int value) {
			this.value = value;
			in = 0;
			out = 0;
			nexts = new ArrayList<>();
			edges = new ArrayList<>();
		}
	}

	public static class Graph {
		public HashMap<Integer, Node> nodes;
		public HashSet<Edge> edges;

		public Graph() {
			nodes = new HashMap<>();
			edges = new HashSet<>();
		}
	}

	public static class NodeRecord {
		public Node node;
		public int distance;

		public NodeRecord(Node node, int distance) {
			this.node = node;
			this.distance = distance;
		}
	}

	public static class NodeHeap {
		private Node[] nodes; // 实际的堆结构
		// key 某一个node， value 上面数组中的位置
		private HashMap<Node, Integer> heapIndexMap;
		// key 某一个节点， value 从源节点出发到该节点的目前最小距离
		private HashMap<Node, Integer> distanceMap;
		private int size; // 堆上有多少个点

		public NodeHeap(int size) {
			nodes = new Node[size];
			heapIndexMap = new HashMap<>();
			distanceMap = new HashMap<>();
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
		// 判断要不要更新，如果需要的话，就更新
		public void addOrUpdateOrIgnore(Node node, int distance) {
			if (inHeap(node)) {
				distanceMap.put(node, Math.min(distanceMap.get(node), distance));
				insertHeapify(node, heapIndexMap.get(node));
			}
			if (!isEntered(node)) {
				nodes[size] = node;
				heapIndexMap.put(node, size);
				distanceMap.put(node, distance);
				insertHeapify(node, size++);
			}
		}

		public NodeRecord pop() {
			NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
			swap(0, size - 1);
			heapIndexMap.put(nodes[size - 1], -1);
			distanceMap.remove(nodes[size - 1]);
			// free C++同学还要把原本堆顶节点析构，对java同学不必
			nodes[size - 1] = null;
			heapify(0, --size);
			return nodeRecord;
		}

		private void insertHeapify(Node node, int index) {
			while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
				swap(index, (index - 1) / 2);
				index = (index - 1) / 2;
			}
		}

		private void heapify(int index, int size) {
			int left = index * 2 + 1;
			while (left < size) {
				int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
						? left + 1
						: left;
				smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
				if (smallest == index) {
					break;
				}
				swap(smallest, index);
				index = smallest;
				left = index * 2 + 1;
			}
		}

		private boolean isEntered(Node node) {
			return heapIndexMap.containsKey(node);
		}

		private boolean inHeap(Node node) {
			return isEntered(node) && heapIndexMap.get(node) != -1;
		}

		private void swap(int index1, int index2) {
			heapIndexMap.put(nodes[index1], index2);
			heapIndexMap.put(nodes[index2], index1);
			Node tmp = nodes[index1];
			nodes[index1] = nodes[index2];
			nodes[index2] = tmp;
		}
	}

	// matrix 所有的边
	// N*3 的矩阵
	// [weight, from节点上面的值，to节点上面的值]
	public static Graph createGraph(int[][] matrix) {
		Graph graph = new Graph();

		for (int i = 0; i < matrix.length; i++) { // matrix[0][0], matrix[0][1] matrix[0][2]
			Integer from = matrix[i][0];
			Integer to = matrix[i][1];
			Integer weight = matrix[i][2];

			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}

			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);

			Edge newEdge = new Edge(weight, fromNode, toNode);
			fromNode.nexts.add(toNode);
			fromNode.out++;
			toNode.in++;

			fromNode.edges.add(newEdge);
			graph.edges.add(newEdge);
		}

		return graph;
	}

	// 改进后的dijkstra算法
	// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
	public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
		HashMap<Node, Integer> result = new HashMap<>();
		if (head == null) {
			result.put(head, 0);
			return result;
		}

		NodeHeap nodeHeap = new NodeHeap(size);
		nodeHeap.addOrUpdateOrIgnore(head, 0);

		while (!nodeHeap.isEmpty()) {
			NodeRecord record = nodeHeap.pop();
			Node cur = record.node;
			int distance = record.distance;

			if (cur != null) {
				for (Edge edge : cur.edges) {
					nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
				}
			}

			result.put(cur, distance);
		}

		return result;
	}

	public static class DistanceNode {
		public Node node;
		public int dis;

		public DistanceNode(Node v, int dis) {
			this.node = v;
			this.dis = dis;
		}

		@Override
		public String toString() {
			return "DistanceNode [node=" + node + ", dis=" + dis + "]";
		}
	}

	// MinHeap
	public static class DistanceNodeComparator implements Comparator<DistanceNode> {
		@Override
		public int compare(DistanceNode o1, DistanceNode o2) {
			return o1.dis - o2.dis;
		}
	}

	public static HashMap<Node, Integer> dijkstra1(Node head) {

		// 从head出发到所有点的最小距离
		// key : 从head出发到达key
		// value : 从head出发到达key的最小距离
		// 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
		HashMap<Node, Integer> distanceMap = new HashMap<>();
		if (head == null) {
			distanceMap.put(head, 0);
			return distanceMap;
		}
		distanceMap.put(head, 0);
		// 已经求过距离的节点，存在selectedNodes中，以后再也不碰
		HashSet<Node> selectedNodes = new HashSet<>();
		selectedNodes.add(null);

		PriorityQueue<DistanceNode> queue = new PriorityQueue<>(new DistanceNodeComparator());
		DistanceNode headDistanceMap = new DistanceNode(head, 0);
		queue.add(headDistanceMap);

		while (!queue.isEmpty()) {
			DistanceNode minNode = queue.poll();

			if (!selectedNodes.contains(minNode.node)) {
				int distance = distanceMap.get(minNode.node);

				for (Edge edge : minNode.node.edges) {
					Node toNode = edge.to;
					if (selectedNodes.contains(toNode))
						continue;

					if (!distanceMap.containsKey(toNode)) {
						distanceMap.put(toNode, distance + edge.weight);
					} else {
						distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
					}

					selectedNodes.add(minNode.node);
					DistanceNode toDistanceMap = new DistanceNode(toNode, distanceMap.get(toNode));
					queue.add(toDistanceMap);
				}
			}
		}
		return distanceMap;
	}

	public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
		Node minNode = null;
		int minDistance = Integer.MAX_VALUE;
		for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
			Node node = entry.getKey();
			int distance = entry.getValue();
			if (!touchedNodes.contains(node) && distance < minDistance) {
				minNode = node;
				minDistance = distance;
			}
		}
		return minNode;
	}

//	https://blog.csdn.net/qq_35644234/article/details/60870719
//	1 3 10
//	1 5 30
//	1 6 100
//	2 3 5
//	3 4 50
//	4 6 10
//	5 6 60
//	5 4 20

//	起点  终点               最短路径       长度
//	v1    v2            无                     ∞    
//	      v3     {v1,v3}    10
//	      v4     {v1,v5,v4}  50
//	      v5     {v1,v5}    30
//	      v6     {v1，v5,v4,v6} 60
	public static void main(String[] args) {
		int[][] matrix = new int[][] { { 1, 3, 10 }, { 1, 5, 30 }, { 1, 6, 100 }, { 2, 3, 5 }, { 3, 4, 50 },
				{ 4, 6, 10 }, { 5, 6, 60 }, { 5, 4, 20 } };
		Graph graph = createGraph(matrix);
		HashMap<Node, Integer> dMap = dijkstra2(graph.nodes.get(1), 6);
//		HashMap<Node, Integer> dMap = dijkstra1(graph.nodes.get(1));
		for (Node key : dMap.keySet()) {
			Integer value = dMap.get(key);
			System.out.println("path = " + key.path + ", Key = " + key.value + ", Value = " + value);
		}
	}

}
